package com.leetcode.listnode.demo7;

import java.util.HashSet;
import java.util.Set;

/**
 * @Author Zan
 * @Create 2024/5/15 10:13
 * @ClassName: Test
 * @Description : https://leetcode.cn/problems/linked-list-cycle-ii/description/  环形链表 II
 */
public class Test {
    public static void main(String[] args) {

    }
}

// HashSet的写法
class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> sets = new HashSet<>();
        while (pos != null) {
            if (sets.contains(pos)) {
                return pos;
            } else {
                sets.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
}

// 快慢指针
class Solution2 {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {// 有环
                ListNode index1 = fast;
                ListNode index2 = head;
                // 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode(int val) {
        this.val = val;
    }
}